package dp.一维数组;

import java.util.Arrays;
import java.util.Comparator;

/**
 https://leetcode.cn/problems/russian-doll-envelopes/
 *
 * 题解：https://mp.weixin.qq.com/s/Z_hNXjB2Q1tf7JgJ-_SSCQ
 */
public class _354_俄罗斯套娃信封问题 {

    public int maxEnvelopes(int[][] envelopes) {
        // 先将数组进行排序，第一列正序，如果第一列相等，第二列倒序。因为第一列相等的话，后面的元素不应该包括前面的元素
        Arrays.sort(envelopes, (a1, b1) -> a1[0] == b1[0] ? b1[1] - a1[1] : a1[0] - b1[0]);
        int[] dp = new int[envelopes.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }

        }

        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }

}
